package tulingxueyuan117;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 快速升序排序（很重要）
 */
public class p39_计数排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        int[] res = countingSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }
    public static int[] countingSort(int[] nums) {
        if(nums.length==0) return nums;
        int bias, min = nums[0], max = nums[0];  // 找最大值和最小值以及偏移量，用于定义原始数组每个元素在计数数组中的下标位置
        for(int i=1; i<nums.length; i++){
            if(nums[i]>max)
                max = nums[i];
            if(nums[i]<min)
                min = nums[i];
        }
        bias = 0-min;
        int[] counterArray = new int[max-min+1];  // 获得计数数组的容量
        Arrays.fill(counterArray, 0);
        for(int i=0; i<nums.length; i++){
            counterArray[nums[i]+bias]++;
        }
        int index = 0;  // 访问原始数组时的下标计时器
        int i = 0;  // 访问计数数组时的下标计数器
//        访问计数数组，将计数数组中的元素转换后，重新写会原始数组
        while (index<nums.length){
//            只要计数数组中当前下标元素不为零，就将计数数组中的元素转换后重新写会原始数组
            if(counterArray[i]!=0){
                nums[index] = i - bias;
                counterArray[i]--;
                index++;
            }else {
                i++;
            }
        }
        return nums;
    }
}
